package LeetCode;

import java.util.LinkedList;

public class LC_331_VerifyPreorderSerializationofaBinaryTree {

    public static void main(String[] args) {

    }

    static class Solution {
        public boolean isValidSerialization(String preorder) {
            LinkedList<String> stack = new LinkedList<String>();
            String[] arr = preorder.split(",");
            for (String anArr : arr) {
                stack.add(anArr);
                while (stack.size() >= 3 && stack.get(stack.size() - 1).equals("#")
                        && stack.get(stack.size() - 2).equals("#") && !stack.get(stack.size() - 3).equals("#")) {
                    stack.remove(stack.size() - 1);
                    stack.remove(stack.size() - 1);
                    stack.remove(stack.size() - 1);
                    stack.add("#");
                }
            }
            return stack.size() == 1 && stack.get(0).equals("#");
        }

    }
}